// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package ssa

// Shortcircuit查找分支方向
// 始终相关的情况，并重写CFG以利用该事实。
// 此优化对于编译&&和| |表达式非常有用。
func shortcircuit(f *Func) {
	// 步骤1：如果参数
	// 是前一个if块的控制值，则用常量替换phi arg。
	// b1:
	// 如果转到b2其他b3 
	// b2:<-b1。。。
	// x=phi（a，…）
	// 
	// 我们可以用常数true替换phi中的“a”。
	var ct, cf *Value
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			if v.Op != OpPhi {
				continue
			}
			if !v.Type.IsBoolean() {
				continue
			}
			for i, a := range v.Args {
				e := b.Preds[i]
				p := e.b
				if p.Kind != BlockIf {
					continue
				}
				if p.Controls[0] != a {
					continue
				}
				if e.i == 0 {
					if ct == nil {
						ct = f.ConstBool(f.Config.Types.Bool, true)
					}
					v.SetArg(i, ct)
				} else {
					if cf == nil {
						cf = f.ConstBool(f.Config.Types.Bool, false)
					}
					v.SetArg(i, cf)
				}
			}
		}
	}

	// 步骤2：围绕已知分支重定向控制流。
	// p:
	// 。。。转到b。。。
	// b:<-p。。。
	// v=phi（真，…）
	// 如果v转到t else u 
	// 我们可以重定向p直接转到t而不是b.
	// （如果v在b之后不活动）。
	fuse(f, fuseTypePlain|fuseTypeShortCircuit)
}

// shortcircuitBlock检查一个CFG，其中一个If块
// 的控制值是一个带有ConstBool arg的Phi。
// 在某些情况下，我们可以将CFG重写为更平坦的形式。
// 
// （1）查找格式为
// 
// p其他pred 
// \/
// b 
// \
// t其他成功
// 
// /其中b是一个包含一个phi值的If块，只使用一次（b的控件），
// 它有一个ConstBool arg。
// p是与在其中找到ConstBool的参数槽相对应的前置。
// t是与ConstBool arg的值相对应的后继值。
// 
// 将其改写为
// 
// p其他pred 
// /|/
// /| b 
// /|87
// 
// 并删除相应的phi arg。
// 
// （2）寻找形式为
// 
// p q 
// \/
// b 
// \
// t u 
// 
// ，其中b如（1）所述。
// 但是，b也可能包含其他phi值。
// CFG将按照（1）所述进行修改。
// 然而，为了处理其他的phi值，
// 对于彼此的phi值w，我们必须能够从b中消除w。
// 我们可以这样做，尽管将w移动到不同的块
// 并重写使用w来使用不同的值。
// 详见短路方案。
func shortcircuitBlock(b *Block) bool {
	if b.Kind != BlockIf {
		return false
	}
	// 查找表单Copy的控制值（Not（Copy（Phi（const，…）））。
	// 这些必须是b中唯一的值，并且每个值只能由b使用。
	// 跟踪否定，以便我们以后可以根据需要交换后续值。
	ctl := b.Controls[0]
	nval := 1 // 控制值
	var swap int64
	for ctl.Uses == 1 && ctl.Block == b && (ctl.Op == OpCopy || ctl.Op == OpNot) {
		if ctl.Op == OpNot {
			swap = 1 ^ swap
		}
		ctl = ctl.Args[0]
		nval++ // 包装控制值
	}
	if ctl.Op != OpPhi || ctl.Block != b || ctl.Uses != 1 {
		return false
	}
	nOtherPhi := 0
	for _, w := range b.Values {
		if w.Op == OpPhi && w != ctl {
			nOtherPhi++
		}
	}
	if nOtherPhi > 0 && len(b.Preds) != 2 {
		// 我们依赖于b在shortcircuitPhiPlan 
		// 中正好有两个pred来推断PHI的值。
		return false
	}
	if len(b.Values) != nval+nOtherPhi {
		return false
	}
	if nOtherPhi > 0 {
		// 检查是否有任何phi是另一个phi的参数。
		// 这些情况很棘手，因为替换使用
		// 在任何排序中都不再是微不足道的。见第45175期。
		m := make(map[*Value]bool, 1+nOtherPhi)
		for _, v := range b.Values {
			if v.Op == OpPhi {
				m[v] = true
			}
		}
		for v := range m {
			for _, a := range v.Args {
				if a != v && m[a] {
					return false
				}
			}
		}
	}

	// 找到第一个常数phi arg的索引。
	cidx := -1
	for i, a := range ctl.Args {
		if a.Op == OpConstBool {
			cidx = i
			break
		}
	}
	if cidx == -1 {
		return false
	}

	// p是对应于cidx的前置。
	pe := b.Preds[cidx]
	p := pe.b
	pi := pe.i

	// t是“take”分支：当我们从p.
	ti := 1 ^ ctl.Args[cidx].AuxInt ^ swap
	te := b.Succs[ti]
	t := te.b
	if p == b || t == b {
		// 进入时，我们总是去的继任者，这是一个无限循环；我们不能移除它。见第33903期。
		return false
	}

	var fixPhi func(*Value, int)
	if nOtherPhi > 0 {
		fixPhi = shortcircuitPhiPlan(b, ctl, cidx, ti)
		if fixPhi == nil {
			return false
		}
	}

	// 我们已经承诺了。更新CFG和Phis。
	// 如果修改此部分，请更新相应的shortcircuitPhiPlan。wen jian efg

	b.removePred(cidx)
	b.removePhiArg(ctl, cidx)

	p.Succs[pi] = Edge{t, len(t.Preds)}

	t.Preds = append(t.Preds, Edge{p, pi})
	for _, v := range t.Values {
		if v.Op != OpPhi {
			continue
		}
		v.AddArg(v.Args[te.i])
	}

	if nOtherPhi != 0 {
		// 根据需要调整所有其他潜在危险装置。
		// 使用普通for循环代替range，因为fixPhi可能会移动phis，
		// 从而修改b.值。
		for i := 0; i < len(b.Values); i++ {
			phi := b.Values[i]
			if phi.Uses == 0 || phi == ctl || phi.Op != OpPhi {
				continue
			}
			fixPhi(phi, i)
			if phi.Block == b {
				continue
			}
			// phi和v.moveTo被转移到了另一个街区。
			// 将此新块中引用
			// 的phi值调整为引用相应的phi参数。
			// phi在该区块之前被评估过，
			// 现在在这个模块中进行评估。
			for _, v := range phi.Block.Values {
				if v.Op != OpPhi || v == phi {
					continue
				}
				for j, a := range v.Args {
					if a == phi {
						v.SetArg(j, phi.Args[j])
					}
				}
			}
			if phi.Uses != 0 {
				phielimValue(phi)
			} else {
				phi.reset(OpInvalid)
			}
			i-- // v.move在索引i处添加一个新值；重新处理
		}

		// 我们可能留下了一些phi值，但没有使用
		// 但是参数的数量错误。消除这些。
		for _, v := range b.Values {
			if v.Uses == 0 {
				v.reset(OpInvalid)
			}
		}
	}

	if len(b.Preds) == 0 {
		// 布洛克现在死了。
		b.Kind = BlockInvalid
	}

	phielimValue(ctl)
	return true
}

// shortcircuitPhiPlan返回一个函数来处理b中的非ctl phi值，其中b如shortcircuitBlock中所述。
// 返回的函数接受一个值v 
// 和v.Block中v的索引i:v.Block。值[i]==v.
// 如果返回的函数将v移动到另一个块，它将使用v.moveTo。
// cidx是ConstBool参数的ctl中的索引。
// ti是b中的索引。当从p到达时，总是执行的分支的成功。
// 如果shortcircuitPhiPlan返回nil，则没有可用的计划，
// 并且CFG修改不能继续。
// 返回的函数假定shortcircuitBlock已完成其CFG修改。
func shortcircuitPhiPlan(b *Block, ctl *Value, cidx int, ti int64) func(*Value, int) {
	// t是“已采取的”分支：我们从p进来时总是去的继任者。
	t := b.Succs[ti].b
	// u是“未采取的”分支：我们从p进来时从不去的继任者。
	u := b.Succs[1^ti].b

	// 在下面的CFG匹配中，确保b的PreD与b的成功完全不同。
	// 这可能是一个比要求更强的条件，但这种情况极为罕见，
	// 而且它更容易避免被漂亮的ASCII图表欺骗。见#44465。
	if p0, p1 := b.Preds[0].b, b.Preds[1].b; p0 == t || p1 == t || p0 == u || p1 == u {
		return nil
	}

	// 寻找一些常见的CFG结构
	// 其中来自b的出站路径合并，
	// 没有其他PreD加入它们。
	// 在这些情况下，我们可以重建b中任何phi的值
	// 在后续块中必须是什么。

	if len(t.Preds) == 1 && len(t.Succs) == 1 &&
		len(u.Preds) == 1 && len(u.Succs) == 1 &&
		t.Succs[0].b == u.Succs[0].b && len(t.Succs[0].b.Preds) == 2 {
		// p q 
		// \/
		// b 
		// \
		// /t u 
		// \/
		// m 
		// 
		// ，这看起来像是
		// 
		// p q 
		// |/
		// | b 
		// |/\
		// t u 
		// 
		// 
		// NB。
		m := t.Succs[0].b
		return func(v *Value, i int) {
			// 将v在t和u中的任何用法替换为v必须具有的值，
			// 考虑到我们已经到达了该区块。
			// 然后将v移动到m，并相应地调整其值；
			// p q 
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			u.replaceUses(v, argQ)
			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
			phi.AddArg2(argQ, argP)
			t.replaceUses(v, phi)
			if v.Uses == 0 {
				return
			}
			v.moveTo(m, i)
			if m.Preds[0].b == t {
				v.SetArgs2(phi, argQ)
			} else {
				v.SetArgs2(argQ, phi)
			}
		}
	}

	if len(t.Preds) == 2 && len(u.Preds) == 1 && len(u.Succs) == 1 && u.Succs[0].b == t {
		// /\/
		// b 
		// /|
		// /| u 
		// /| 
		// 
		// q 
		// 
		// b 
		// | \
		// p | u 
		// |/
		// t 
		// 
		// NB。
		return func(v *Value, i int) {
			// /替换v在u中的任何用法。然后将v移到t。
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			u.replaceUses(v, argQ)
			v.moveTo(t, i)
			v.SetArgs3(argQ, argQ, argP)
		}
	}

	if len(u.Preds) == 2 && len(t.Preds) == 1 && len(t.Succs) == 1 && t.Succs[0].b == u {
		// p q 
		// \/
		// b 
		// ；
		// t | 
		// \\\124; 
		// 
		// ，这看起来像是
		// 
		// p q 
		// /|/
		// /| b 
		// ；
		// t | 
		// /| 
		// u 
		// 
		return func(v *Value, i int) {
			// 替换t中v的任何用法。然后将v移到u。
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
			phi.AddArg2(argQ, argP)
			t.replaceUses(v, phi)
			if v.Uses == 0 {
				return
			}
			v.moveTo(u, i)
			v.SetArgs2(argQ, phi)
		}
	}

	// 寻找一些常见的CFG结构
	// 其中一个出站路径从b退出，
	// 没有其他PreD加入。
	// 在这些情况下，我们可以重建b中任何phi的值
	// 必须位于通向出口的路径中，
	// 并将phi移动到非出口路径。

	if len(t.Preds) == 1 && len(u.Preds) == 1 && len(t.Succs) == 0 {
		// p q 
		// \/
		// b 
		// \
		// /t u 
		// /
		// /其中t是出口/出口块。
		// 
		// 在CFG修改后，这将看起来像
		// 
		// p q 
		// /|/
		// /| b 
		// /|/\
		// tu 
		// 
		// NB:t.Preds是（b，p），不是（p，b）。
		return func(v *Value, i int) {
			// 替换t和x中v的任何用法。然后将v移到u。
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			// 如果t或x中没有v的用法，则此phi将不使用。
			// 没关系；不值得为此付出代价。
			phi := t.Func.newValue(OpPhi, v.Type, t, v.Pos)
			phi.AddArg2(argQ, argP)
			t.replaceUses(v, phi)
			if v.Uses == 0 {
				return
			}
			v.moveTo(u, i)
			v.SetArgs1(argQ)
		}
	}

	if len(u.Preds) == 1 && len(t.Preds) == 1 && len(u.Succs) == 0 {
		// p q 
		// \/
		// b 
		// \
		// /t u 
		// 
		// /其中u是出口/出口区块。CDEFG
		// 在CFG修改后，这看起来像是
		// 
		// p q 
		// |/
		// | b 
		// |/\
		// t u 
		// 
		// /NB。
		return func(v *Value, i int) {
			// 替换u（和x）中v的任何用法。然后转到t.
			argP, argQ := v.Args[cidx], v.Args[1^cidx]
			u.replaceUses(v, argQ)
			v.moveTo(t, i)
			v.SetArgs2(argQ, argP)
		}
	}

	// TODO:处理更多案件；结果证明，短路优化具有相当高的影响
	return nil
}

// replaceUses将b中的所有旧功能替换为新功能。
func (b *Block) replaceUses(old, new *Value) {
	for _, v := range b.Values {
		for i, a := range v.Args {
			if a == old {
				v.SetArg(i, new)
			}
		}
	}
	for i, v := range b.ControlValues() {
		if v == old {
			b.ReplaceControl(i, new)
		}
	}
}

// moveTo将v移动到dst，调整相应的块。价值观切片。
// 呼叫方负责确保安全。
// i是v块中v的索引。价值观
func (v *Value) moveTo(dst *Block, i int) {
	if dst.Func.scheduled {
		v.Fatalf("moveTo after scheduling")
	}
	src := v.Block
	if src.Values[i] != v {
		v.Fatalf("moveTo bad index %d", v, i)
	}
	if src == dst {
		return
	}
	v.Block = dst
	dst.Values = append(dst.Values, v)
	last := len(src.Values) - 1
	src.Values[i] = src.Values[last]
	src.Values[last] = nil
	src.Values = src.Values[:last]
}
